package com.itzmn.newcode.offer1;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;
import java.util.concurrent.Executors;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/20 18:54
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 二叉搜索树与双向链表
 *
 *  输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，
 *  只能调整树中结点指针的指向
 *
 *  使用非递归中序遍历，将指针改变
 *
 */
public class _26_BinarySearchTreeAndDoublyLinkedList extends Tree{



    public static void main(String[] args) {
        new _26_BinarySearchTreeAndDoublyLinkedList().test();

    }

    private void test() {
        TreeNode binarySearchTree = createBinarySearchTree(new int[]{10, 5, 15, 3, 7, 12, 17});
        InOrderTraversal(binarySearchTree);
        Convert(binarySearchTree);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {

        boolean isFirst = true;
        TreeNode root = null;
        TreeNode pre = null;
        if (pRootOfTree != null){
            Stack<TreeNode> stack = new Stack<>();
            // 中序遍历，先输出左节点，输出根，输出右子树，所以先压最左子树，在压右子树
            while (!stack.isEmpty() || pRootOfTree != null){
                // 如果还没走到最左。一直赋值左节点
                if (pRootOfTree != null){
                    stack.push(pRootOfTree);
                    pRootOfTree = pRootOfTree.left;
                }else {
                    // 如果抵达了最左，那么弹出父亲，输出，然后赋值右子树
                    pRootOfTree = stack.pop();
                    if (isFirst){
                        root = pRootOfTree;
                        pre = pRootOfTree;
                        isFirst = false;
                    }else {
                        pre.right = pRootOfTree;
                        pRootOfTree.left = pre;
                        pre = pRootOfTree;
                    }
                    System.out.print(pRootOfTree.val+" ");
                    pRootOfTree = pRootOfTree.right;
                }
            }
        }
        return root;

    }


}
